COCI/2010-2011/Contest #1 - 22.10.2010/ples/ples.cpp

   1 // Andrés Mejía
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const double EPS = 1e-9;
  29 int cmp(double x, double y = 0, double tol = EPS) {
  30     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  31 }
  32
  33
  34 const int MAXH = 1501;
  35
  36 /////////////// Maximum flow for sparse graphs ///////////////
  37 ///////////////    Complexity: O(V * E^2)      ///////////////
  38
  39 /*
  40 Usage:
  41 initialize_max_flow();
  42 Create graph using add_edge(u, v, c);
  43 max_flow(source, sink);
  44
  45 WARNING: The algorithm writes on the cap array. The capacity
  46 is not the same after having run the algorithm.  If you need
  47 to run the algorithm several times on the same graph, backup
  48 the cap array.
  49 */
  50
  51 namespace Flow {
  52     const int MAXN = MAXH * 4 + 2;
  53     const int MAXE = (MAXH * (MAXH + 1) + 4 * MAXH); //Maximum number of edges
  54     const int oo = INT_MAX / 4;
  55
  56     int first[MAXN];
  57     int next[MAXE];
  58     int adj[MAXE];
  59     unsigned short cap[MAXE];
  60     int current_edge;
  61
  62     /*
  63     Builds a directed edge (u, v) with capacity c.
  64     Note that actually two edges are added, the edge
  65     and its complementary edge for the backflow.
  66     */
  67     int add_edge(int u, int v, int c){
  68         adj[current_edge] = v;
  69         cap[current_edge] = c;
  70         next[current_edge] = first[u];
  71         first[u] = current_edge++;
  72
  73         adj[current_edge] = u;
  74         cap[current_edge] = 0;
  75         next[current_edge] = first[v];
  76         first[v] = current_edge++;
  77     }
  78
  79     void initialize_max_flow(){
  80         current_edge = 0;
  81         memset(next, -1, sizeof next);
  82         memset(first, -1, sizeof first);
  83     }
  84
  85     short q[MAXN];
  86     int arrived_by[MAXN];
  87     //arrived_by[i] = The last edge used to reach node i
  88     int find_augmenting_path(int src, int snk){
  89         /*
  90         Make a BFS to find an augmenting path from the source to
  91         the sink.  Then pump flow through this path, and return
  92         the amount that was pumped.
  93         */
  94         memset(arrived_by, -1, sizeof arrived_by);
  95         int h = 0, t = 0;
  96         q[t++] = src;
  97         arrived_by[src] = -2;
  98         while (h < t && arrived_by[snk] == -1){ //BFS
  99             int u = q[h++];
 100             for (int e = first[u]; e != -1; e = next[e]){
 101                 int v = adj[e];
 102                 if (arrived_by[v] == -1 && cap[e] > 0){
 103                     arrived_by[v] = e;
 104                     q[t++] = v;
 105                 }
 106             }
 107         }
 108
 109         if (arrived_by[snk] == -1) return 0;
 110
 111         int cur = snk;
 112         int neck = oo;
 113         while (cur != src) {
 114             if (cap[arrived_by[cur]] < neck) neck = cap[arrived_by[cur]];
 115             cur = adj[arrived_by[cur] ^ 1];
 116         }
 117
 118         cur = snk;
 119         while (cur != src){
 120             //Remove capacity from the edge used to reach node "cur"
 121             //Add capacity to the backedge
 122             cap[arrived_by[cur]] -= neck;
 123             cap[arrived_by[cur] ^ 1] += neck;
 124             //move backwards in the path
 125             cur = adj[arrived_by[cur] ^ 1];
 126         }
 127         return neck;
 128     }
 129
 130     int max_flow(int src, int snk){
 131         int ans = 0, neck;
 132         while ((neck = find_augmenting_path(src, snk)) != 0){
 133             ans += neck;
 134         }
 135         return ans;
 136     }
 137 }
 138
 139 const int src = MAXH * 4, sink = src + 1;
 140
 141 int face(int number, bool isBoy) {
 142     int ans = isBoy ? 0 : 2 * MAXH;
 143     if (number < 0) ans += -number;
 144     else ans += number + MAXH;
 145     ans -= 1500;
 146     //printf("number = %d, isBoy = %d, ans = %d\n", number, isBoy, ans);
 147     assert(ans < 4 * MAXH);
 148     return ans;
 149 }
 150
 151 unsigned short cnt[4 * MAXH];
 152
 153 int main(){
 154     //D(Flow::maxedge);
 155     int n;
 156     scanf("%d", &n);
 157     for (int i = 0; i < n; ++i) {
 158         int x; scanf("%d", &x);
 159         assert(1500 <= abs(x) and abs(x) <= 2500);
 160         int k = face(x, true);
 161         cnt[k]++;
 162         //printf("cnt[boy = %d] = %d\n", x, cnt[k]);
 163     }
 164     for (int i = 0; i < n; ++i) {
 165         int x; scanf("%d", &x);
 166         assert(1500 <= abs(x) and abs(x) <= 2500);
 167         int k = face(x, false);
 168         cnt[k]++;
 169         //printf("cnt[girl = %d] = %d\n", x, cnt[k]);
 170     }
 171
 172     //Flow::init(Flow::maxnode, src, sink);
 173     Flow::initialize_max_flow();
 174
 175     for (int boy = -2500; boy <= -1500; ++boy) {
 176         if (cnt[face(boy, true)] == 0) continue;
 177         for (int girl = 1500; girl < -boy; ++girl) {
 178             if (cnt[face(girl, false)] == 0) continue;
 179             Flow::add_edge(face(boy, true), face(girl, false), Flow::oo);
 180             //printf("Added edge from boy = %d to girl = %d\n", boy, girl);
 181         }
 182     }
 183
 184     for (int boy = 1500; boy <= 2500; ++boy) {
 185         if (cnt[face(boy, true)] == 0) continue;
 186         for (int girl = -boy-1; girl >= -2500; --girl) {
 187             if (cnt[face(girl, false)] == 0) continue;
 188             Flow::add_edge(face(boy, true), face(girl, false), Flow::oo);
 189             //printf("Added edge from boy = %d to girl = %d\n", boy, girl);
 190         }
 191     }
 192
 193     for (int k = 1500; k <= 2500; ++k) {
 194         if (cnt[face(k, true)] > 0) {
 195             Flow::add_edge(src, face(k, true), cnt[face(k, true)]);
 196         }
 197         if (cnt[face(-k, true)] > 0) {
 198             Flow::add_edge(src, face(-k, true), cnt[face(-k, true)]);
 199         }
 200
 201         if (cnt[face(k, false)] > 0) {
 202             Flow::add_edge(face(k, false), sink, cnt[face(k, false)]);
 203         }
 204
 205         if (cnt[face(-k, false)] > 0) {
 206             Flow::add_edge(face(-k, false), sink, cnt[face(-k, false)]);
 207         }
 208     }
 209
 210     //int ans = Flow::dinic_flow();
 211     int ans = Flow::max_flow(src, sink);
 212     cout << ans << endl;
 213     return 0;
 214 }